home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / glass / glass.lha / GLASS / tm / refex.c < prev    next >
C/C++ Source or Header  |  1990-11-06  |  11KB  |  466 lines
  1. /* 
  2.    Copyright (C) 1990 C van Reewijk, email: dutentb.uucp!reeuwijk
  3.  
  4. This file is part of GLASS.
  5.  
  6. GLASS is free software; you can redistribute it and/or modify
  7. it under the terms of the GNU General Public License as published by
  8. the Free Software Foundation; either version 1, or (at your option)
  9. any later version.
  10.  
  11. GLASS is distributed in the hope that it will be useful,
  12. but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14. GNU General Public License for more details.
  15.  
  16. You should have received a copy of the GNU General Public License
  17. along with GLASS; see the file COPYING.  If not, write to
  18. the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  19.  
  20. /* File: refex.c
  21.  *
  22.  * refex - File regular expression pattern matching
  23.  *         and replacement
  24.  *
  25.  * By:  Ozan S. Yigit (oz)
  26.  *      Dept. of Computer Science
  27.  *      York University
  28.  *
  29.  * Munged by C. van Reeuwijk to do shell style pattern matching.
  30.  * {} shell patterns are not handled.
  31.  *
  32.  * These routines are the PUBLIC DOMAIN equivalents
  33.  * of refex routines as found in 4.nBSD UN*X, with minor
  34.  * extensions.
  35.  *
  36.  * These routines are derived from various implementations
  37.  * found in software tools books, and Conroy's grep. They
  38.  * are NOT derived from licensed/restricted software.
  39.  * For more interesting/academic/complicated implementations,
  40.  * see Henry Spencer's refexp routines, or GNU Emacs pattern
  41.  * matching module.
  42.  *
  43.  * Routines:
  44.  *      ref_comp:        compile a regular expression into a DFA.
  45.  *
  46.  *            char *ref_comp(s)
  47.  *            char *s;
  48.  *
  49.  *      ref_exec:       execute the DFA to match a pattern.
  50.  *
  51.  *            int ref_exec(s)
  52.  *            char *s;
  53.  *
  54.  *      ref_subs:    substitute the matched portions in
  55.  *                  a new string.
  56.  *
  57.  *            int ref_subs(src, dst)
  58.  *            char *src;
  59.  *            char *dst;
  60.  *
  61.  * Regular Expressions:
  62.  *
  63.  *      [1]     char    matches itself, unless it is a special
  64.  *                      character (metachar): . \ [ ] * + ^ $
  65.  *
  66.  *      [2]     ?       matches any character.
  67.  *
  68.  *      [3]     \       matches the character following it, except
  69.  *            when followed by a digit 1 to 9.
  70.  *            (see [7], [8] and [9])
  71.  *            It is used as an escape character for all
  72.  *            other meta-characters, and itself. When used
  73.  *            in a set ([4]), it is treated as an ordinary
  74.  *            character.
  75.  *
  76.  *      [4]     [set]   matches one of the characters in the set.
  77.  *                      If the first character in the set is "^",
  78.  *                      it matches a character NOT in the set. A
  79.  *                      shorthand S-E is used to specify a set of
  80.  *                      characters S upto E, inclusive. The special
  81.  *                      characters "]" and "-" have no special
  82.  *                      meaning if they appear as the first chars
  83.  *                      in the set.
  84.  *                      examples:        match:
  85.  *
  86.  *                              [a-z]    any lowercase alpha
  87.  *
  88.  *                              [^]-]    any char except ] and -
  89.  *
  90.  *                              [^A-Z]   any char except uppercase
  91.  *                                       alpha
  92.  *
  93.  *                              [a-zA-Z] any alpha
  94.  *
  95.  *      [5]     *       matches the longest possible span of zero or more
  96.  *                      arbitrary characters.
  97.  *
  98.  *      [6]             a regular expression in the form [1] to [10], enclosed
  99.  *                      as (form) matches what form matches. The enclosure
  100.  *                      creates a set of tags, used for pattern substution.
  101.  *                      The tagged forms are numbered starting from 1.
  102.  *
  103.  *      [7]             a composite regular expression xy where x and y
  104.  *                      are in the form [1] to [7] matches x followed by
  105.  *                      a match for y.
  106.  *
  107.  * Acknowledgements:
  108.  *
  109.  *    HCR's Hugh Redelmeier has been most helpful in various
  110.  *    stages of development. He convinced me to include BOW
  111.  *    and EOW constructs, originally invented by Rob Pike at
  112.  *    the University of Toronto.
  113.  *
  114.  * References:
  115.  *              Software tools            Kernighan & Plauger
  116.  *              Software tools in Pascal        Kernighan & Plauger
  117.  *              Grep [rsx-11 C dist]            David Conroy
  118.  *        ed - text editor        Un*x Programmer's Manual
  119.  *        Advanced editing on Un*x    B. W. Kernighan
  120.  *        RegExp routines            Henry Spencer
  121.  *
  122.  * Notes:
  123.  *
  124.  *    This implementation uses a bit-set representation for character
  125.  *    classes for speed and compactness. Each character is represented
  126.  *    by one bit in a 128-bit block. Thus, CCL or NCL always takes a
  127.  *    constant 16 bytes in the internal dfa, and ref_exec does a single
  128.  *    bit comparison to locate the character in the set.
  129.  *
  130.  * Examples:
  131.  *
  132.  *    pattern:    fo*
  133.  *    compile:    CHR f CHR o star END
  134.  *    matches:    fo foo fooo foobar fobar foxx ...
  135.  *
  136.  *    pattern:    fo[ob]a[rz]
  137.  *    compile:    CHR f CHR o CCL bitset CHR a CCL bitset END
  138.  *    matches:    fobar fooar fobaz fooaz
  139.  *
  140.  *    pattern:    (foo)[1-3]
  141.  *    compile:    BOT 1 CHR f CHR o CHR o EOT 1 CCL bitset END
  142.  *    matches:    foo1 foo2 foo3
  143.  *
  144.  *    pattern:    (fo*)-
  145.  *    compile:    BOT 1 CHR f CHR o STAR EOT 1 CHR - END
  146.  *    matches:    foo- fo- fob- foobar-
  147.  *
  148.  */
  149.  
  150. #include <stdio.h>
  151. #include "refex.h"
  152.  
  153. #define MAXDFA  1024
  154. #define MAXTAG  10
  155.  
  156. #define OKP     1
  157. #define NOP     0
  158.  
  159. #define CHR     1
  160. #define ANY     2
  161. #define CCL     3
  162. #define NCL     4
  163. #define BOT     7
  164. #define EOT     8
  165. #define STAR   13
  166.  
  167. #define END     0
  168.  
  169. /*
  170.  * The following defines are not meant
  171.  * to be changeable. They are for readibility
  172.  * only.
  173.  *
  174.  */
  175. #define MAXCHR    128
  176. #define CHRBIT    8
  177. #define BITBLK    MAXCHR/CHRBIT
  178. #define BLKIND    0170
  179. #define BITIND    07
  180.  
  181. #define ASCIIB    0177
  182.  
  183. typedef /*unsigned*/ char CHAR;
  184.  
  185. static int  tagstk[MAXTAG];             /* subpat tag stack..*/
  186. static CHAR dfa[MAXDFA];        /* automaton..       */
  187. static int  sta = NOP;                   /* status of lastpat */
  188.  
  189. static CHAR bittab[BITBLK];        /* bit table for CCL */
  190.  
  191. static void chset( c )
  192.  register CHAR c;
  193. {
  194.     bittab[((c)&BLKIND)>>3] |= 1<<((c)&BITIND);
  195. }
  196.  
  197. #define badpat(x)    return(*dfa = END, x)
  198. #define store(x)    *mp++ = x
  199.  
  200. char *ref_comp(pat)
  201. char *pat;
  202. {
  203.     register char *p;               /* pattern pointer   */
  204.     register CHAR *mp=dfa;          /* dfa pointer       */
  205.  
  206.     register int tagi = 0;          /* tag stack index   */
  207.     register int tagc = 1;          /* actual tag count  */
  208.  
  209.     register int n;
  210.     int c1, c2;
  211.  
  212.     if (!pat || !*pat)
  213.     if (sta)
  214.         return( 0 );
  215.     else
  216.         badpat("No previous regular expression");
  217.     sta = NOP;
  218.  
  219.     for (p = pat; *p != '\0'; p++) {
  220.     switch(*p){
  221.         case '?':               /* match any char..  */
  222.         store(ANY);
  223.         break;
  224.  
  225.         case '[':               /* match char class..*/
  226.         if (*++p == '^') {
  227.             store(NCL);
  228.             p++;
  229.         }
  230.         else
  231.             store(CCL);
  232.  
  233.         if (*p == '-')        /* real dash */
  234.             chset(*p++);
  235.         if (*p == ']')        /* real brac */
  236.             chset(*p++);
  237.         while (*p && *p != ']') {
  238.             if (*p == '-' && *(p+1) && *(p+1) != ']') {
  239.             p++;
  240.             c1 = *(p-2) + 1;
  241.             c2 = *p++;
  242.             while (c1 <= c2)
  243.                 chset(c1++);
  244.             }
  245.             else
  246.             chset(*p++);
  247.         }
  248.         if (!*p)
  249.             badpat("Missing ]");
  250.  
  251.         for (n = 0; n < BITBLK; bittab[n++] = (char) 0)
  252.             store(bittab[n]);
  253.  
  254.         break;
  255.  
  256.         case '*':               /* match 0 or more.. */
  257.         store(STAR);
  258.         break;
  259.  
  260.         case '(':
  261.         if( tagc>=MAXTAG ){
  262.             badpat( "Too many () pairs" );
  263.         }
  264.         tagstk[++tagi] = tagc;
  265.         store(BOT);
  266.         store(tagc++);
  267.         break;
  268.         
  269.         case ')':
  270.         if( tagi<=0 ){
  271.             badpat( "Unmatched )" );
  272.         }
  273.         store( EOT );
  274.         store( tagstk[tagi--] );
  275.         break;
  276.  
  277.         case '\\':              /* tags, backrefs .. */
  278.         p++;
  279.         store(CHR);
  280.         store(*p);
  281.         break;
  282.  
  283.         default :               /* an ordinary char  */
  284.         store(CHR);
  285.         store(*p);
  286.         break;
  287.     }
  288.     }
  289.     if (tagi > 0)
  290.         badpat("Unmatched \\(");
  291.     store(END);
  292.     sta = OKP;
  293.     return( 0 );
  294. }
  295.  
  296. static char *bopat[MAXTAG];
  297. static char *eopat[MAXTAG];
  298. static char *pmatch();
  299.  
  300. /*
  301.  * ref_exec:
  302.  *     execute dfa to match the string.
  303.  *
  304.  *    If the pattern matches, bopat[0] and eopat[0] are set
  305.  *    to the beginning and the end of the matched fragment,
  306.  *    respectively.
  307.  *
  308.  * return 1 if the compiled pattern matches the given string,
  309.  * or else 0.
  310.  */
  311.  
  312. int ref_exec(lp)
  313.  register char *lp;
  314. {
  315.     register char *ep = 0;
  316.     register CHAR *ap = dfa;
  317.  
  318.     bopat[0] = 0;
  319.     bopat[1] = 0;
  320.     bopat[2] = 0;
  321.     bopat[3] = 0;
  322.     bopat[4] = 0;
  323.     bopat[5] = 0;
  324.     bopat[6] = 0;
  325.     bopat[7] = 0;
  326.     bopat[8] = 0;
  327.     bopat[9] = 0;
  328.  
  329.     if( *ap == END ) return( 0 );    /* munged automaton. fail always */
  330.     ep = pmatch( lp, ap );
  331.     if (!ep)
  332.     return( 0 );
  333.     bopat[0] = lp;
  334.     eopat[0] = ep;
  335.     return(1);
  336. }
  337.  
  338. /*
  339.  * pmatch:
  340.  *    internal routine for the hard part
  341.  *
  342.  *     This code is mostly snarfed from an early
  343.  *     grep written by David Conroy. The backref and
  344.  *     tag stuff, and various other mods are by oZ.
  345.  *
  346.  *    At the end of a successful match, bopat[n] and eopat[n]
  347.  *    are set to the beginning and end of subpatterns matched
  348.  *    by tagged expressions (n = 1 to 9).
  349.  *
  350.  */
  351.  
  352. #define isinset(x,y)     ((x)[((y)&BLKIND)>>3] & (1<<((y)&BITIND)))
  353.  
  354. static char *pmatch( lp, ap )
  355. register char *lp;
  356. register CHAR *ap;
  357. {
  358.     register char *e;        /* extra pointer for CLO */
  359.     register int op;
  360.     register int c;
  361.     char *are;            /* to save the line ptr. */
  362.  
  363.     for(;;){
  364.     op = *ap++;
  365.     if( op == END ) break;
  366.     switch(op) {
  367.         case CHR:
  368.         if (*lp++ != *ap++)
  369.             return( 0 );
  370.         break;
  371.  
  372.         case ANY:
  373.         if (*lp++ == '\0' )
  374.             return( 0 );
  375.         break;
  376.  
  377.         case CCL:
  378.         c = *lp++;
  379.         if (!isinset(ap,c))
  380.             return( 0 );
  381.         ap += BITBLK;
  382.         break;
  383.  
  384.         case NCL:
  385.         c = *lp++;
  386.         if (isinset(ap,c))
  387.             return( 0 );
  388.         ap += BITBLK;
  389.         break;
  390.  
  391.         case BOT:
  392.         bopat[*ap++] = lp;
  393.         break;
  394.  
  395.         case EOT:
  396.         eopat[*ap++] = lp;
  397.         break;
  398.  
  399.         case STAR:
  400.         are = lp;
  401.         while (*lp) lp++;
  402.         while( lp >= are ){
  403.             if( e = pmatch( lp, ap) ) return( e );
  404.             --lp;
  405.         }
  406.         return( 0 );
  407.  
  408.         default:
  409.         fprintf( stderr, "ref_exec: bad dfa opcode: %d.\n", op );
  410.         exit( 2 );
  411.     }
  412.     }
  413.     if( *lp != '\0' ) return( 0 );
  414.     return( lp );
  415. }
  416.  
  417. /* Substitute the matched portions of the 'src' in 'dst'.
  418.  * The following special characters are recognized in 'src':
  419.  *
  420.  * &:
  421.  *    Substitute the entire matched pattern.
  422.  *
  423.  * \digit:
  424.  *    Substitute a subpattern, with the given tag number. Tags are
  425.  *    numbered from 1 to 9. If the particular tagged subpattern
  426.  *     does not exist, the empty string is substituted.
  427.  */
  428. void ref_subs( src, dst )
  429.  register char *src;
  430.  register char *dst;
  431. {
  432.     register char c;
  433.     register int pin;
  434.     register char *bp;
  435.     register char *ep;
  436.  
  437.     if( !*src || !bopat[0] )
  438.     return;
  439.  
  440.     while( c = *src++ ){
  441.     switch(c) {
  442.         case '&':
  443.         pin = 0;
  444.         break;
  445.  
  446.         case '\\':
  447.         c = *src++;
  448.         if (c >= '0' && c <= '9') {
  449.             pin = c - '0';
  450.             break;
  451.         }
  452.  
  453.         default:
  454.         *dst++ = c;
  455.         continue;
  456.         }
  457.         bp = bopat[pin];
  458.         ep = eopat[pin];
  459.         if( bp && ep ){
  460.         while( *bp != '\0' && bp < ep )
  461.             *dst++ = *bp++;
  462.         }
  463.     }
  464.     *dst = '\0';
  465. }
  466.